{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sparse Matrix Multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: multiply"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #稀疏矩阵的乘法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个&nbsp;<a href=\"https://baike.baidu.com/item/%E7%A8%80%E7%96%8F%E7%9F%A9%E9%98%B5\" target=\"_blank\">稀疏矩阵</a>&nbsp;：大小为 <code>m x k</code> 的稀疏矩阵 <code>mat1</code> 和大小为 <code>k x n</code> 的稀疏矩阵 <code>mat2</code> ，返回 <code>mat1 x mat2</code> 的结果。你可以假设乘法总是可能的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/12/mult-grid.jpg\" style=\"height: 142px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]\n",
    "<strong>输出：</strong>[[7,0,0],[-7,0,3]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>&nbsp;示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>mat1 = [[0]], mat2 = [[0]]\n",
    "<b>输出：</b>[[0]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat1.length</code></li>\n",
    "\t<li><code>k == mat1[i].length == mat2.length</code></li>\n",
    "\t<li><code>n == mat2[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n, k &lt;= 100</code></li>\n",
    "\t<li><code>-100 &lt;= mat1[i][j], mat2[i][j] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sparse-matrix-multiplication](https://leetcode.cn/problems/sparse-matrix-multiplication/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sparse-matrix-multiplication](https://leetcode.cn/problems/sparse-matrix-multiplication/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,0],[-1,0,3]]\\n[[7,0,0],[0,0,0],[0,0,1]]', '[[0]]\\n[[0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0] * len(mat2[0]) for _ in range(len(mat1))]\n",
    "\n",
    "        for row_index, row_elements in enumerate(mat1):\n",
    "            for element_index, row_element in enumerate(row_elements):\n",
    "                if row_element:\n",
    "                    for col_index, col_element in enumerate(mat2[element_index]):\n",
    "                        ans[row_index][col_index] += row_element * col_element\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m,h,n = len(mat1),len(mat1[0]),len(mat2[0])\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for k in range(h):\n",
    "                if mat1[i][k]==0: continue\n",
    "                for j in range(n):\n",
    "                    res[i][j]+=mat1[i][k]*mat2[k][j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat1), len(mat2[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(len(mat2)):\n",
    "                    ans[i][j] += mat1[i][k] * mat2[k][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        r1, c1 = len(mat1), len(mat1[0])\n",
    "        r2, c2 = len(mat2), len(mat2[0])\n",
    "        res = [[0] * c2 for i in range(r1)] # r1 rows, c2 cols\n",
    "\n",
    "        for r in range(r1):\n",
    "            for col in range(c2):\n",
    "                temp = 0\n",
    "                for c in range(c1):\n",
    "                    temp += mat1[r][c] * mat2[c][col]\n",
    "                res[r][col] = temp\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        r_mat1=defaultdict(set)\n",
    "        c_mat2=defaultdict(set)\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat1[0])):\n",
    "                if mat1[i][j]:\n",
    "                    r_mat1[i].add(j)\n",
    "\n",
    "        for i in range(len(mat2)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                if mat2[i][j]:\n",
    "\n",
    "                    c_mat2[j].add(i)\n",
    "\n",
    "        ans=[[0]*(len(mat2[0]))  for i in range(len(mat1))]\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                if i in r_mat1 and j in c_mat2:\n",
    "                    t=0\n",
    "                    v=r_mat1[i]&c_mat2[j]\n",
    "                    for v1 in v:\n",
    "                        # if v1 in c_mat2[j]:\n",
    "                        t+=mat1[i][v1]*mat2[v1][j]\n",
    "                    \n",
    "                    ans[i][j]=t\n",
    "        return ans\n",
    "\n",
    "        # ans = [[0] * len(mat2[0]) for _ in range(len(mat1))]\n",
    "        \n",
    "        # for row_index, row_elements in enumerate(mat1):\n",
    "        #     for element_index, row_element in enumerate(row_elements):\n",
    "        #         # 如果 mat1 的当前元素非零，则遍历 mat2 的所有列。\n",
    "        #         if row_element:\n",
    "        #             for col_index, col_element in enumerate(mat2[element_index]):\n",
    "        #                 ans[row_index][col_index] += row_element * col_element\n",
    "        \n",
    "        # return ans\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        aa = self.get_non_zero(mat1)\n",
    "        bb = self.get_non_zero(mat2)\n",
    "        n = len(mat1)\n",
    "        m = len(mat2[0])\n",
    "        C = [[0]*m for _ in range(n)] \n",
    "        for va, i,j in aa:\n",
    "            for vb,x,y in bb:\n",
    "                if j==x:\n",
    "                    C[i][y]+=va*vb\n",
    "        return C\n",
    "\n",
    "\n",
    "\n",
    "    def get_non_zero(self,A):\n",
    "        n = len(A)\n",
    "        m = len(A[0])\n",
    "        res =[]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if A[i][j]!=0:\n",
    "                    res.append((A[i][j],i,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat1)\n",
    "        k = len(mat2)\n",
    "        n = len(mat2[0])\n",
    "        ans = [[0 for i in range(n)] for i in range(m)]\n",
    "        \n",
    "        need_row_ids = set()\n",
    "        triples = []\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j]:\n",
    "                    triples.append([i, j, mat1[i][j]])\n",
    "                    need_row_ids.add(j)\n",
    "        \n",
    "        row2val = collections.defaultdict(list)\n",
    "        for row in list(need_row_ids):\n",
    "            for col, val in enumerate(mat2[row]):\n",
    "                if val:\n",
    "                    row2val[row].append([val, col])\n",
    "        for [row1, col1, val1] in triples:\n",
    "            for [val2, col2] in row2val[col1]:\n",
    "                ans[row1][col2] += val1 * val2\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        def parse(mat):\n",
    "            res = []\n",
    "            for i in range(len(mat)):\n",
    "                for j in range(len(mat[0])):\n",
    "                    if mat[i][j]:\n",
    "                        res.append((i, j, mat[i][j]))\n",
    "            return res\n",
    "        \n",
    "        mat1_p = parse(mat1)\n",
    "        mat2_p = parse(mat2)\n",
    "        res = [[0 for j in range(len(mat2[0]))] for i in range(len(mat1))]\n",
    "        for i1, j1, x1 in mat1_p:\n",
    "            for i2, j2, x2 in mat2_p:\n",
    "                if j1 == i2:\n",
    "                    res[i1][j2] += x1 * x2 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "#         m, k, n = len(mat1), len(mat1[0]), len(mat2[0])\n",
    "#         res = [[0] * n for _ in range(m)]\n",
    "#         for i in range(m):\n",
    "#             for j in range(k):\n",
    "#                 if mat1[i][j]:\n",
    "#                     for x in range(n):\n",
    "#                         res[i][x] += mat1[i][j] * mat2[j][x]\n",
    "#         return res\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, k, n = len(mat1), len(mat1[0]), len(mat2[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        dic1 = collections.defaultdict(int)\n",
    "        dic2 = collections.defaultdict(int)\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j]:\n",
    "                    dic1[(i, j)] += mat1[i][j]\n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j]:\n",
    "                    dic2[(i, j)] += mat2[i][j]\n",
    "        for k1, v1 in dic1.items():\n",
    "            for k2, v2 in dic2.items():\n",
    "                x1, y1 = k1\n",
    "                x2, y2 = k2\n",
    "                if y1 == x2:\n",
    "                    res[x1][y2] += v1 * v2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "                # m = len(mat1)\n",
    "        # k = len(mat1[0]) \n",
    "        # k = len(mat2)\n",
    "        # n = len(mat2[0])\n",
    "        # \"\"\" 结果为 m * n \"\"\"\n",
    "        # res = [ [0]*n for _ in range(m)]\n",
    "        # for i in range(m):\n",
    "        #     for z in range(n): \n",
    "        #         if mat1[i][z]: #不为 0 就继续，省略0 的情况，节省时间\n",
    "        #             for j in range(k):\n",
    "                    \n",
    "        #                 res[i][z] +=(mat1[i][j]*mat2[j][z] )\n",
    "        # return res \n",
    "        m = len(mat1)\n",
    "        k = len(mat1[0]) \n",
    "        n = len(mat2[0])\n",
    "        hash1 = defaultdict(int)\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j] != 0:\n",
    "                    hash1[(i,j)] = mat1[i][j]\n",
    "        hash2 = defaultdict(int)\n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j] != 0:\n",
    "                    hash2[(i,j)] = mat2[i][j]\n",
    "        res = [ [0]*n for i in range(m)]\n",
    "        for k1,v1 in hash1.items():\n",
    "            for k2,v2 in hash2.items():\n",
    "                if k1[1] == k2[0]: # mat1行 与 mat2列对应\n",
    "                    res[k1[0]][k2[1]] += v1*v2\n",
    "        return res         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        mat1Triple = []\n",
    "        rowSet = set()\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat1[0])):\n",
    "                if mat1[i][j] != 0:\n",
    "                    mat1Triple.append([mat1[i][j], i, j])\n",
    "                    rowSet.add(j)\n",
    "\n",
    "        mat2Pair = defaultdict(list) # rowPairs\n",
    "        for j in rowSet:\n",
    "            for k in range(len(mat2[0])):\n",
    "                if mat2[j][k] != 0:\n",
    "                    mat2Pair[j].append([mat2[j][k], k])\n",
    "\n",
    "        res = [[0] * len(mat2[0]) for _ in range(len(mat1))]\n",
    "        for val1, x1, y1 in mat1Triple:\n",
    "            for val2, y2 in mat2Pair[y1]:\n",
    "                res[x1][y2] += val1 * val2\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "\n",
    "\n",
    "        n, k = len(mat1), len(mat1[0])\n",
    "        k, m = len(mat2), len(mat2[0])\n",
    "        def getSparseRepresentation(A):\n",
    "            posList = []\n",
    "            m = len(A)\n",
    "            n = len(A[0])\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if A[i][j] != 0:\n",
    "                        posList.append([A[i][j],i,j])\n",
    "            return posList\n",
    "\n",
    "        mat1dense = getSparseRepresentation(mat1)\n",
    "        mat2dense = getSparseRepresentation(mat2)\n",
    "\n",
    "        res = [[0 for j in range(m)] for i in range(n)]\n",
    "\n",
    "\n",
    "        for v1, i, j in mat1dense:\n",
    "\n",
    "            for v2 , a, b in mat2dense:\n",
    "\n",
    "                if j == a:\n",
    "\n",
    "                    res[i][b] +=v1 * v2\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        list1 = []\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat1[0])):\n",
    "                if mat1[i][j]!=0: list1.append((i,j,mat1[i][j]))\n",
    "\n",
    "        list2 = []\n",
    "        for i in range(len(mat2)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                if mat2[i][j]!=0: list2.append((i,j,mat2[i][j]))\n",
    "        \n",
    "        result = [[0 for _ in range(len(mat2[0]))] for _ in range(len(mat1))]\n",
    "        for i1, j1, v1 in list1:\n",
    "            for i2, j2, v2 in list2:\n",
    "                if j1 == i2: result[i1][j2] += v1 * v2\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0]*len(mat2[0]) for _ in range(len(mat1))]\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                col = [mat2[k][j] for k in range(len(mat2))]\n",
    "                mul = sum([mat1[i][l] * col[l] for l in range(len(mat2))])\n",
    "                res[i][j] = mul\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        def compress_matrix(matrix: List[List[int]]) -> List[List[int]]:\n",
    "            rows, cols = len(matrix), len(matrix[0])\n",
    "            compressed_matrix = [[] for _ in range(rows)]\n",
    "            for row in range(rows):\n",
    "                for col in range(cols):\n",
    "                    if matrix[row][col]:\n",
    "                        compressed_matrix[row].append([matrix[row][col], col])\n",
    "            return compressed_matrix\n",
    "        \n",
    "        m = len(mat1)\n",
    "        k = len(mat1[0])\n",
    "        n = len(mat2[0])\n",
    "        \n",
    "        # 存储每个矩阵的非零值。\n",
    "        A = compress_matrix(mat1)\n",
    "        B = compress_matrix(mat2)\n",
    "        \n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        \n",
    "        for mat1_row in range(m):\n",
    "            #  迭代 mat1 的所有当前“行”非零元素。\n",
    "            for element1, mat1_col in A[mat1_row]:\n",
    "                # 将 mat2 中的所有非零元素相乘并相加\n",
    "                # 其中一行等于 mat1 中当前元素的 col。\n",
    "                for element2, mat2_col in B[mat1_col]:\n",
    "                    ans[mat1_row][mat2_col] += element1 * element2\n",
    "                    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat1)\n",
    "        n = len(mat2[0])\n",
    "        k = len(mat1[0])\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for p in range(k):\n",
    "                    ans[i][j] += mat1[i][p] * mat2[p][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat1)\n",
    "        k = len(mat1[0]) \n",
    "        k = len(mat2)\n",
    "        n = len(mat2[0])\n",
    "        \"\"\" 结果为 m * n \"\"\"\n",
    "        res = [ [0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for z in range(n): \n",
    "                \n",
    "                for j in range(k):\n",
    "                 \n",
    "                    res[i][z] +=(mat1[i][j]*mat2[j][z] )\n",
    "        return res \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, k, n = len(mat1), len(mat2), len(mat2[0])\n",
    "\n",
    "        mat1_condense = [None] * m\n",
    "        mat2_condense = [None] * n\n",
    "\n",
    "        for i in range(m):\n",
    "            mat1_condense[i] = [(j, mat1[i][j]) for j in range(k) if mat1[i][j] != 0]\n",
    "\n",
    "        for j in range(n):\n",
    "            mat2_condense[j] = [(i, mat2[i][j]) for i in range(k) if mat2[i][j] != 0]\n",
    "\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a, b = mat1_condense[i], mat2_condense[j]\n",
    "                prod_sum = 0\n",
    "                x, y = 0, 0\n",
    "                while x < len(a) and y < len(b):\n",
    "                    if a[x][0] == b[y][0]:\n",
    "                        prod_sum += a[x][1] * b[y][1]\n",
    "                        x += 1\n",
    "                        y += 1\n",
    "                    elif a[x][0] > b[y][0]:\n",
    "                        y += 1\n",
    "                    elif a[x][0] < b[y][0]:\n",
    "                        x += 1\n",
    "                res[i][j] = prod_sum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        mat1_dict, mat2_dict = defaultdict(int), defaultdict(int)\n",
    "\n",
    "        m1, n1 = len(mat1), len(mat1[0])\n",
    "        m2, n2 = len(mat2), len(mat2[0])\n",
    "        mat1_row, mat2_col = [], []\n",
    "\n",
    "        for r in range(m1):\n",
    "            row = []\n",
    "            for c in range(n1):\n",
    "                v = mat1[r][c]\n",
    "                if v != 0:\n",
    "                    row.append( (c, v) )\n",
    "            mat1_row.append(row)\n",
    "\n",
    "        for c in range(n2):\n",
    "            col = []\n",
    "            for r in range(m2):\n",
    "                v = mat2[r][c]\n",
    "                if v != 0:\n",
    "                    col.append( (r, v) )\n",
    "            mat2_col.append(col)\n",
    "\n",
    "        # print(mat1_row, mat2_col)\n",
    "        \n",
    "        def dotProd(v1, v2):\n",
    "            # print(v1, v2)\n",
    "            p, q = 0, 0\n",
    "            m, n = len(v1), len(v2)\n",
    "            sum_up =0\n",
    "            while p<m and q<n:\n",
    "                idx1, n1 = v1[p]\n",
    "                idx2, n2 = v2[q]\n",
    "                if idx1 == idx2:\n",
    "                    sum_up +=n1*n2\n",
    "                    p+=1\n",
    "                    q+=1\n",
    "                elif idx1 < idx2:\n",
    "                    p+=1\n",
    "                else:\n",
    "                    q+=1\n",
    "            return sum_up\n",
    "\n",
    "        ans = []\n",
    "        for r in range(m1):\n",
    "            row = []\n",
    "            for c in range(n2):\n",
    "                row.append(dotProd(mat1_row[r], mat2_col[c]) )\n",
    "            ans.append(row)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, k, n = len(mat1), len(mat2), len(mat2[0])\n",
    "        list1, list2 = [], []\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j]: list1.append((i,j,mat1[i][j]))\n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j]: list2.append((i,j,mat2[i][j]))\n",
    "        \n",
    "        for i,k,v1 in list1:\n",
    "            # print(\"i={}, k={}, v1={}\".format(i,k,v1))\n",
    "            for k1,j,v2 in list2:\n",
    "                if k == k1:\n",
    "                    res[i][j] += v1*v2\n",
    "                if k < k1: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        mat1Triple = []\n",
    "        rowSet = set()\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat1[0])):\n",
    "                if mat1[i][j] != 0:\n",
    "                    mat1Triple.append([mat1[i][j], i, j])\n",
    "                    rowSet.add(j)\n",
    "\n",
    "        mat2Pair = [[] for _ in range(len(mat2))] # rowPairs\n",
    "        for j in rowSet:\n",
    "            for k in range(len(mat2[0])):\n",
    "                if mat2[j][k] != 0:\n",
    "                    mat2Pair[j].append([mat2[j][k], k])\n",
    "\n",
    "        res = [[0] * len(mat2[0]) for _ in range(len(mat1))]\n",
    "        for val1, x1, y1 in mat1Triple:\n",
    "            for val2, y2 in mat2Pair[y1]:\n",
    "                res[x1][y2] += val1 * val2\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "#         ans = []\n",
    "\n",
    "#         for i in range(len(mat1)):\n",
    "#             ans_sub = []\n",
    "#             for j in range(len(mat2[0])):\n",
    "#                 label = 0\n",
    "#                 for h in range(len(mat2)):\n",
    "#                     label += mat1[i][h] * mat2[h][j]\n",
    "#                 ans_sub.append(label)\n",
    "#             ans.append(ans_sub)\n",
    "#         return ans\n",
    "                \n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        r1 = len(mat1)\n",
    "        r2 = len(mat2)\n",
    "\n",
    "        if r1 == 0 or r2 == 0:\n",
    "            return []\n",
    "        \n",
    "        c1 = len(mat1[0])\n",
    "        c2 = len(mat2[0])\n",
    "\n",
    "        res = [[0] * c2 for _ in range(r1)]\n",
    "        mat1_ = collections.defaultdict(dict)\n",
    "        for r in range(r1):\n",
    "            for c in range(c1):\n",
    "                if mat1[r][c] != 0:\n",
    "                    mat1_[r][c] = mat1[r][c]\n",
    "        \n",
    "        mat2_ = collections.defaultdict(dict)\n",
    "        for c in range(c2):\n",
    "            for r in range(r2):\n",
    "                if mat2[r][c] != 0:\n",
    "                    mat2_[c][r] = mat2[r][c]\n",
    "\n",
    "        \n",
    "        for k1, v1 in mat1_.items():\n",
    "            for k2, v2 in mat2_.items():\n",
    "                res[k1][k2] = sum([v * v2.get(k, 0) for k, v in v1.items()])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat1), len(mat2[0])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a = mat1[i]\n",
    "                b = []\n",
    "                for k in mat2:\n",
    "                    b.append(k[j])\n",
    "                sums = 0\n",
    "                for k,v in zip(a, b):\n",
    "                    sums += k*v\n",
    "                dp[i][j] = sums\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        rowA, colA = len(A), len(A[0]) #mat multiplication [i * j] * [j * k] => [i * k]\n",
    "        colB = len(B[0])\n",
    "        res = [[0] * colB for i in range(rowA)]\n",
    "\n",
    "        for i in range(rowA):\n",
    "            for j in range(colA):\n",
    "                if A[i][j] != 0:\n",
    "                    for k in range(colB):\n",
    "                        if B[j][k] != 0:\n",
    "                            res[i][k] += A[i][j] * B[j][k]\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        # rowA, colA = len(mat1), len(mat1[0]) # [i * j] * [j * k] => [i * k]\n",
    "        # colB = len(mat2[0])\n",
    "        # res = [[0] * colB for i in range(rowA)] # rowA rows, colB cols\n",
    "\n",
    "        # for i in range(rowA):\n",
    "        #     for j in range(colA):\n",
    "        #         if mat1[i][j] != 0:\n",
    "        #             for k in range(colB):\n",
    "        #                 #if either mat1[i][j] or mat2[j][k] == 0, then the res[i][k] increment here is 0\n",
    "        #                 if mat2[j][k] != 0:\n",
    "        #                     res[i][k] += mat1[i][j] * mat2[j][k]\n",
    "\n",
    "        # return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        A = mat1\n",
    "        B = mat2\n",
    "        m = len(A)\n",
    "        n = len(B[0])\n",
    "        posA = self.getSparseRepresentation(A)\n",
    "        posB = self.getSparseRepresentation(B)\n",
    "        res = [[0 for i in range(n)] for j in range(m)]\n",
    "        for valA, xA, yA in posA:\n",
    "            for valB, xB, yB in posB:\n",
    "                if yA == xB:\n",
    "                    res[xA][yB] += valA * valB\n",
    "        return res\n",
    "\n",
    "\n",
    "    def getSparseRepresentation(self, A):\n",
    "        posList = []\n",
    "        m = len(A)\n",
    "        n = len(A[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if A[i][j] != 0:\n",
    "                    posList.append([A[i][j],i,j])\n",
    "        return posList\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        mat1_dict, mat2_dict = defaultdict(int), defaultdict(int)\n",
    "\n",
    "        m1, n1 = len(mat1), len(mat1[0])\n",
    "        m2, n2 = len(mat2), len(mat2[0])\n",
    "        mat1_row, mat2_col = [], []\n",
    "\n",
    "        for r in range(m1):\n",
    "            row = []\n",
    "            for c in range(n1):\n",
    "                v = mat1[r][c]\n",
    "                if v != 0:\n",
    "                    row.append( (c, v) )\n",
    "            mat1_row.append(row)\n",
    "\n",
    "        for c in range(n2):\n",
    "            col = []\n",
    "            for r in range(m2):\n",
    "                v = mat2[r][c]\n",
    "                if v != 0:\n",
    "                    col.append( (r, v) )\n",
    "            mat2_col.append(col)\n",
    "\n",
    "        # print(mat1_row, mat2_col)\n",
    "        \n",
    "        def dotProd(v1, v2):\n",
    "            # print(v1, v2)\n",
    "            p, q = 0, 0\n",
    "            m, n = len(v1), len(v2)\n",
    "            sum_up =0\n",
    "            while p<m and q<n:\n",
    "                idx1, n1 = v1[p]\n",
    "                idx2, n2 = v2[q]\n",
    "                if idx1 == idx2:\n",
    "                    sum_up +=n1*n2\n",
    "                    p+=1\n",
    "                    q+=1\n",
    "                elif idx1 < idx2:\n",
    "                    p+=1\n",
    "                else:\n",
    "                    q+=1\n",
    "            return sum_up\n",
    "\n",
    "        ans = []\n",
    "        for r in range(m1):\n",
    "            row = []\n",
    "            for c in range(n2):\n",
    "                v1, v2 = mat1_row[r], mat2_col[c]\n",
    "                if v1 and v2:\n",
    "                    row.append(dotProd(v1, v2) )\n",
    "                else:\n",
    "                    row.append(0)\n",
    "            ans.append(row)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, n, q = len(mat1), len(mat1[0]), len(mat2[0])\n",
    "        res = [[0] * q for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(q):\n",
    "                for k in range(n):\n",
    "                    res[i][j] += mat1[i][k] * mat2[k][j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getsparse(self, mat):\n",
    "        pos = []\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]!=0:\n",
    "                    pos.append([mat[i][j], i, j])\n",
    "        return pos\n",
    "\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        posA = self.getsparse(mat1)\n",
    "        posB = self.getsparse(mat2)\n",
    "        m = len(mat1)\n",
    "        n = len(mat2[0])\n",
    "        res = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for valA, iA, jA in posA:\n",
    "            for valB, iB, jB in posB:\n",
    "                if jA==iB:\n",
    "                    res[iA][jB] += valA*valB\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0]*len(mat2[0]) for _ in range(len(mat1))]\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                col = [mat2[k][j] for k in range(len(mat2))]\n",
    "                mul = sum([mat1[i][l] * col[l] for l in range(len(mat2)) if mat1[i][l] != 0 or col[l] != 0])\n",
    "                res[i][j] = mul\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, k, n = len(mat1), len(mat2), len(mat2[0])\n",
    "        list1, list2 = [], []\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j]: list1.append((i,j,mat1[i][j]))\n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j]: list2.append((i,j,mat2[i][j]))\n",
    "        \n",
    "        for i,k,v1 in list1:\n",
    "            # print(\"i={}, k={}, v1={}\".format(i,k,v1))\n",
    "            for k1,j,v2 in list2:\n",
    "                if k == k1:\n",
    "                    res[i][j] += v1*v2\n",
    "                if k < k1: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 先生成稀疏的三元组表示，再逐对运算\n",
    "    def multiply(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(A)\n",
    "        n = len(B[0])\n",
    "        posA = self.getSparseRepresentation(A)\n",
    "        posB = self.getSparseRepresentation(B)\n",
    "        res = [[0 for i in range(n)] for j in range(m)]\n",
    "        for valA, xA, yA in posA:\n",
    "            for valB, xB, yB in posB:\n",
    "                if yA == xB:\n",
    "                    res[xA][yB] += valA * valB\n",
    "        return res\n",
    "    \n",
    "    def getSparseRepresentation(self, A: List[List[int]]):\n",
    "        posList = []\n",
    "        m = len(A)\n",
    "        n = len(A[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if A[i][j] != 0:\n",
    "                    posList.append([A[i][j],i,j])\n",
    "        return posList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        m = len(mat1)\n",
    "        k = len(mat2)\n",
    "        n = len(mat2[0])\n",
    "        for i in range(m):\n",
    "            col = []\n",
    "            for j in range(n):\n",
    "                right_col = [mat2[s][j] for s in range(k)]\n",
    "                col.append(sum([left * right for left, right in zip(mat1[i], right_col)]))\n",
    "            res.append(col)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        # 生成矩阵\n",
    "        ans = [[0] * len(mat2[0]) for _ in range(len(mat1))]\n",
    "        \n",
    "        for row_index, row_elements in enumerate(mat1):\n",
    "            for element_index, row_element in enumerate(row_elements):\n",
    "                # 如果 mat1 的当前元素非零，则遍历 mat2 的所有列。\n",
    "                if row_element:\n",
    "                    for col_index, col_element in enumerate(mat2[element_index]):\n",
    "                        ans[row_index][col_index] += row_element * col_element\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, k, n = len(mat1), len(mat2), len(mat2[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                prod_sum = 0\n",
    "                for l in range(k):\n",
    "                    prod_sum += mat1[i][l] * mat2[l][j]\n",
    "                res[i][j] = prod_sum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        def compress_matrix(matrix):\n",
    "            n_rows, n_cols = len(matrix), len(matrix[0])\n",
    "            compressed_matrix = [[] for _ in range(n_rows)]\n",
    "            for row_index in range(n_rows):\n",
    "                for col_index in range(n_cols):\n",
    "                    if matrix[row_index][col_index]:\n",
    "                        compressed_matrix[row_index].append([matrix[row_index][col_index], col_index])\n",
    "            return compressed_matrix\n",
    "\n",
    "        A = compress_matrix(mat1)\n",
    "        B = compress_matrix(mat2)\n",
    "        m, n = len(mat1), len(mat2[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for A_row_index in range(m):\n",
    "            for element_A, A_col_index in A[A_row_index]:\n",
    "                for element_B, B_col_index in B[A_col_index]:\n",
    "                    ans[A_row_index][B_col_index] += element_A * element_B\n",
    "                    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, k, n = len(mat1), len(mat2), len(mat2[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                prod_sum = 0\n",
    "                for l in range(k):\n",
    "                    prod_sum += mat1[i][l] * mat2[l][j]\n",
    "                res[i][j] = prod_sum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m1_sparse = []\n",
    "        m2_sparse = []\n",
    "\n",
    "        m, k, n = len(mat1), len(mat2), len(mat2[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j] != 0:\n",
    "                    m1_sparse.append((i, j, mat1[i][j]))\n",
    "\n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j] != 0:\n",
    "                    m2_sparse.append((i, j, mat2[i][j]))\n",
    "        \n",
    "        # mult\n",
    "        result = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i, k1, val1 in m1_sparse:\n",
    "            for k2, j, val2 in m2_sparse:\n",
    "                if k1 == k2:\n",
    "                    result[i][j] += val1 * val2\n",
    "                if k1 < k2:\n",
    "                    break\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat1)\n",
    "        k = len(mat1[0]) \n",
    "        k= len(mat2)\n",
    "        n = len(mat2[0])\n",
    "        \"\"\" 结果为 m * n \"\"\"\n",
    "        res = [ [0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for z in range(n): \n",
    "                sum_ = 0\n",
    "                for j in range(k):\n",
    "                    sum_ +=(mat1[i][j]*mat2[j][z] )\n",
    "                    res[i][z] =sum_\n",
    "        return res \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m,k = len(mat1),len(mat1[0])\n",
    "\n",
    "        mat1_dict = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j]!=0:\n",
    "                    mat1_dict[i].append((j,mat1[i][j]))\n",
    "        \n",
    "        k,n = len(mat2),len(mat2[0])\n",
    "        mat2_dict = collections.defaultdict(list)\n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j]!=0:\n",
    "                    mat2_dict[j].append((i,mat2[i][j]))\n",
    "\n",
    "        new_mat = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                nums1 = mat1_dict[i]\n",
    "                nums2 = mat2_dict[j]\n",
    "                \n",
    "                p,q = 0,0 \n",
    "                sums = 0 \n",
    "                while p<len(nums1) and q<len(nums2):\n",
    "                    x, v1 = nums1[p]\n",
    "                    y, v2 = nums2[q]\n",
    "                    if x<y:\n",
    "                        p += 1\n",
    "                    elif x>y:\n",
    "                        q += 1\n",
    "                    else:\n",
    "                        sums += v1*v2 \n",
    "                        p += 1\n",
    "                        q += 1\n",
    "                new_mat[i][j] = sums\n",
    "        return new_mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m,h,n = len(mat1),len(mat1[0]),len(mat2[0])\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(h):\n",
    "                    res[i][j]+=mat1[i][k]*mat2[k][j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        # for a given output[i][j] we only need to sum_k mat1[i][k] a* mat2[k][j] for mat1[i][k] or mat2[k][j] != 0\n",
    "        # as a result we just need to register all datapoints that have nonzero entries\n",
    "        # when we calculate newmatrix[i][j], we find all [i][t] and [t][j] in our registered buffers and multiplie them. But actually\n",
    "        # what we can also do is that we go over all the combinations of the registered nonzero entries and accumulate them to the [i][j]-th entry. So the time complexity is n*m\n",
    "\n",
    "        def get_sparse(mat):\n",
    "\n",
    "            m, n = len(mat), len(mat[0])\n",
    "            out = set()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if mat[i][j] != 0:\n",
    "                        out.add((i, j, mat[i][j]))\n",
    "            return out\n",
    "\n",
    "        sparse1 = get_sparse(mat1)\n",
    "        sparse2 = get_sparse(mat2)\n",
    "\n",
    "        m = len(mat1)\n",
    "        n = len(mat2[0])\n",
    "        newmat = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for item1 in sparse1:\n",
    "            i, t1, val_it1 = item1\n",
    "            for item2 in sparse2:\n",
    "                t2, j, val_it2 = item2\n",
    "                if t1 == t2:\n",
    "                    newmat[i][j] += val_it1 * val_it2\n",
    "        \n",
    "        return newmat\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        c = [[0]*len(mat2[0]) for i in range(len(mat1))]\n",
    "    \n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                for k in range(len(mat2)):\n",
    "                    c[i][j] += mat1[i][k] * mat2[k][j]\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        res = [[0] * len(mat2[0]) for _ in range(len(mat1))]\n",
    "\n",
    "        for row_index,row_elements in enumerate(mat1):\n",
    "            for element_index, row_element in enumerate(row_elements):\n",
    "                for col_index, col_element in enumerate(mat2[element_index]):\n",
    "                    res[row_index][col_index] += row_element * col_element\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0] * len(mat2[0]) for _ in range(len(mat1))]\n",
    "\n",
    "        for row_index,row_elements in enumerate(mat1):\n",
    "            for element_index, row_element in enumerate(row_elements):\n",
    "                for col_index, col_element in enumerate(mat2[element_index]):\n",
    "                    res[row_index][col_index] += row_element * col_element\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat1)\n",
    "        n = len(mat2[0])\n",
    "        temp = [0 for _ in range(n)]\n",
    "        res = [temp.copy() for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(len(mat2)):\n",
    "                    # print(i,j,k)\n",
    "                    # print(mat1[i][k], mat2[k][j])\n",
    "                    if mat1[i][k]==0 or mat2[k][j]==0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        res[i][j] += mat1[i][k]*mat2[k][j]\n",
    "                    # print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:  \n",
    "        m,k,n=len(mat1),len(mat1[0]),len(mat2[0])\n",
    "        ans=[[0 for j in range(n)] for i in range(m)]\n",
    "        def getAns(x,y):\n",
    "            \n",
    "            res=0\n",
    "            for i in range(k):\n",
    "                # try:?\n",
    "                res+=mat1[x][i]*mat2[i][y]\n",
    "                # except:\n",
    "                #     print(x,i,i,y)\n",
    "            return res\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j]=getAns(i,j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        def collectSparsePos(mat):\n",
    "            pos = []\n",
    "            for i in range(len(mat)):\n",
    "                for j in range(len(mat[0])):\n",
    "                    if mat[i][j] != 0:\n",
    "                        pos.append([mat[i][j], i, j])\n",
    "            return pos\n",
    "\n",
    "        mat1Sparse = collectSparsePos(mat1)\n",
    "        mat2Sparse = collectSparsePos(mat2)\n",
    "\n",
    "        res = [[0] * len(mat2[0]) for _ in range(len(mat1))]\n",
    "        for val1, x1, y1 in mat1Sparse:\n",
    "            for val2, x2, y2 in mat2Sparse:\n",
    "                if y1 == x2:\n",
    "                    res[x1][y2] += val1 * val2\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, k, n = len(mat1), len(mat2), len(mat2[0])\n",
    "        list1, list2 = [], []\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j]: list1.append((i,j,mat1[i][j]))\n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j]: list2.append((i,j,mat2[i][j]))\n",
    "        \n",
    "        for i,k,v1 in list1:\n",
    "            # print(\"i={}, k={}, v1={}\".format(i,k,v1))\n",
    "            for k1,j,v2 in list2:\n",
    "                if k == k1:\n",
    "                    res[i][j] += v1*v2\n",
    "                if k < k1: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat1)\n",
    "        n = len(mat2[0])\n",
    "        k = len(mat2)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for p in range(k):\n",
    "                    if mat1[i][p] != 0 and mat2[p][j] != 0:\n",
    "                        # print(mat1[i][p], mat2[p][j], i, j)\n",
    "                        dp[i][j] += mat1[i][p]*mat2[p][j]\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0] * len(mat2[0]) for _ in range(len(mat1))]\n",
    "\n",
    "        for r1, r in enumerate(mat1):\n",
    "            for ei, re in enumerate(r):\n",
    "                if re:\n",
    "                    for c_i, c in enumerate(mat2[ei]):\n",
    "                        ans[r1][c_i] += re*c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, k, n = len(mat1), len(mat2), len(mat2[0])\n",
    "        list1, list2 = [], []\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j]: list1.append((i,j,mat1[i][j]))\n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j]: list2.append((i,j,mat2[i][j]))\n",
    "        \n",
    "        for i,k,v1 in list1:\n",
    "            # print(\"i={}, k={}, v1={}\".format(i,k,v1))\n",
    "            for k1,j,v2 in list2:\n",
    "                if k == k1:\n",
    "                    res[i][j] += v1*v2\n",
    "                if k < k1: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0] * len(mat2[0]) for _ in range(len(mat1))]\n",
    "\n",
    "        for row_index,row_elements in enumerate(mat1):\n",
    "            for element_index, row_element in enumerate(row_elements):\n",
    "                if row_element:\n",
    "                    for col_index, col_element in enumerate(mat2[element_index]):\n",
    "                        res[row_index][col_index] += row_element * col_element\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        A = mat1\n",
    "        B = mat2\n",
    "        m = len(A)\n",
    "        n = len(B[0])\n",
    "        posA = self.getSparseRepresentation(A)\n",
    "        posB = self.getSparseRepresentation(B)\n",
    "        res = [[0 for i in range(n)] for j in range(m)]\n",
    "        for valA, xA, yA in posA:\n",
    "            for valB, xB, yB in posB:\n",
    "                if yA == xB:\n",
    "                    res[xA][yB] += valA * valB\n",
    "        return res\n",
    "    \n",
    "    def getSparseRepresentation(self, A):\n",
    "        posList = []\n",
    "        m = len(A)\n",
    "        n = len(A[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if A[i][j] != 0:\n",
    "                    posList.append([A[i][j],i,j])\n",
    "        return posList\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        counter = {}\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat1[0])):\n",
    "                if mat1[i][j] != 0:\n",
    "                    if i not in counter:\n",
    "                        counter[i] = [mat1[i][j] * k for k in mat2[j]]\n",
    "                    else:\n",
    "                        temp = counter[i]\n",
    "                        counter[i] = [x + mat1[i][j] * y for (x, y) in zip(temp, mat2[j])]\n",
    "                else:\n",
    "                    if i not in counter:\n",
    "                        counter[i] = [0 for k in mat2[j]]\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(mat1)):\n",
    "            res.append(counter[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0] * len(mat2[0]) for _ in range(len(mat1))]\n",
    "\n",
    "        for row_index,row_elements in enumerate(mat1):\n",
    "            for element_index, row_element in enumerate(row_elements):\n",
    "                # if row_element:\n",
    "                for col_index, col_element in enumerate(mat2[element_index]):\n",
    "                    res[row_index][col_index] += row_element * col_element\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, k, n = len(mat1), len(mat2), len(mat2[0])\n",
    "        list1, list2 = [], []\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j]: list1.append((i,j,mat1[i][j]))\n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j]: list2.append((i,j,mat2[i][j]))\n",
    "        \n",
    "        for i,k,v1 in list1:\n",
    "            # print(\"i={}, k={}, v1={}\".format(i,k,v1))\n",
    "            for k1,j,v2 in list2:\n",
    "                if k == k1:\n",
    "                    res[i][j] += v1*v2\n",
    "                if k < k1: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat1)\n",
    "        k = len(mat1[0])\n",
    "        n = len(mat2[0])\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "        for row in range(m):\n",
    "            for colomn in range(n):\n",
    "                index = 0\n",
    "                tmp = 0\n",
    "                while index<k:\n",
    "                    tmp += mat1[row][index]*mat2[index][colomn]\n",
    "                    index +=1 \n",
    "                ans[row][colomn] = tmp \n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        mat_1_row_dict = defaultdict(set)\n",
    "        mat_2_col_dict = defaultdict(set)\n",
    "\n",
    "        m = len(mat1)\n",
    "        k = len(mat1[0])\n",
    "        n = len(mat2[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j] != 0:\n",
    "                    mat_1_row_dict[i].add(j)\n",
    "        \n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j] != 0:\n",
    "                    mat_2_col_dict[j].add(i)\n",
    "\n",
    "        result = [[9] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                index_list = mat_1_row_dict[i].intersection(mat_2_col_dict[j])\n",
    "                value = 0\n",
    "                for idx in index_list:\n",
    "                    value += mat1[i][idx] * mat2[idx][j]\n",
    "                result[i][j] = value\n",
    "        \n",
    "        return result\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m, k = len(mat1), len(mat1[0])\n",
    "        k, n = len(mat2), len(mat2[0])\n",
    "        mat2_r = list(zip(*mat2))\n",
    "        def getNum(l1, l2):\n",
    "            res = 0\n",
    "            for i, j in zip(l1,l2):\n",
    "                res += i * j\n",
    "            return res\n",
    "        ans = [[getNum(mat1[i], mat2_r[j]) for j in range(n)] for i in range(m)]\n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        A = mat1\n",
    "        B = mat2\n",
    "        m = len(A)\n",
    "        n = len(B[0])\n",
    "        posA = self.getSparseRepresentation(A)\n",
    "        posB = self.getSparseRepresentation(B)\n",
    "        out = [[0 for i in range(n)] for j in range(m)]\n",
    "        for valA, xA, yA in posA:\n",
    "            for valB, xB, yB in posB:\n",
    "                if yA == xB: # like Aik *Bkj as this is the only part that needs calculatation\n",
    "                    out[xA][yB] += valA * valB\n",
    "        return out\n",
    "\n",
    "\n",
    "    def getSparseRepresentation(self, A):\n",
    "        out = []\n",
    "        m = len(A)\n",
    "        n = len(A[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if A[i][j] != 0: # will perform during matrix multiplicaiton\n",
    "                    out.append([A[i][j], i, j])\n",
    "        return out\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(mat1)\n",
    "        k=len(mat2)\n",
    "        n=len(mat2[0])\n",
    "        mat1_dict={i:[] for i in range(k)}\n",
    "        mat2_dict={i:[] for i in range(k)}\n",
    "        ans=[[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                if mat1[i][j]!=0:\n",
    "                    mat1_dict[j].append((i,mat1[i][j]))\n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                if mat2[i][j]!=0:\n",
    "                    mat2_dict[i].append((j,mat2[i][j]))\n",
    "        for i in range(k):\n",
    "            for ele1 in mat1_dict[i]:\n",
    "                for ele2 in mat2_dict[i]:\n",
    "                    ans[ele1[0]][ele2[0]]+=ele1[1]*ele2[1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        mat1_nums = dict()\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat1[0])):\n",
    "                if mat1[i][j] != 0:\n",
    "                    mat1_nums[(i, j)] = mat1[i][j]\n",
    "\n",
    "        mat2_nums = dict()\n",
    "        for i in range(len(mat2)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                if mat2[i][j] != 0:\n",
    "                    mat2_nums[(i, j)] = mat2[i][j]\n",
    "        \n",
    "        result = [[0 for _ in range(len(mat2[0]))] for _ in range(len(mat1))]\n",
    "        for i in range(len(result)):\n",
    "            for j in range(len(result[0])):\n",
    "                cur_num = 0\n",
    "\n",
    "                mat1_pairs = set()\n",
    "                mat2_pairs = set()\n",
    "                for pair, num in mat1_nums.items():\n",
    "                    if pair[0] == i:\n",
    "                        mat1_pairs.add(pair[1])\n",
    "                for pair, num in mat2_nums.items():\n",
    "                    if pair[1] == j:\n",
    "                        mat2_pairs.add(pair[0])\n",
    "                need_add = mat1_pairs.intersection(mat2_pairs)\n",
    "                for need_add_num in need_add:\n",
    "                    cur_num += mat1_nums[(i, need_add_num)]*mat2_nums[(need_add_num, j)]\n",
    "                \n",
    "                result[i][j] = cur_num\n",
    "        \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        r_mat1=defaultdict(list)\n",
    "        # c_mat1={}\n",
    "        # r_mat2={}\n",
    "        c_mat2=defaultdict(list)\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat1[0])):\n",
    "                r_mat1[i].append(j)\n",
    "\n",
    "        for i in range(len(mat2)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                c_mat2[j].append(i)\n",
    "\n",
    "        ans=[[0]*(len(mat2[0]))  for i in range(len(mat1))]\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                if i in r_mat1 and j in c_mat2:\n",
    "                    t=0\n",
    "                    for v1 in r_mat1[i]:\n",
    "                        if v1 in c_mat2[j]:\n",
    "                            t+=mat1[i][v1]*mat2[v1][j]\n",
    "                    \n",
    "                    ans[i][j]=t\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        r_mat1=defaultdict(set)\n",
    "        # c_mat1={}\n",
    "        # r_mat2={}\n",
    "        c_mat2=defaultdict(set)\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat1[0])):\n",
    "                r_mat1[i].add(j)\n",
    "\n",
    "        for i in range(len(mat2)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                c_mat2[j].add(i)\n",
    "\n",
    "        ans=[[0]*(len(mat2[0]))  for i in range(len(mat1))]\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                if i in r_mat1 and j in c_mat2:\n",
    "                    t=0\n",
    "                    v=r_mat1[i]&c_mat2[j]\n",
    "                    for v1 in v:\n",
    "                        # if v1 in c_mat2[j]:\n",
    "                        t+=mat1[i][v1]*mat2[v1][j]\n",
    "                    \n",
    "                    ans[i][j]=t\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        r_mat1=defaultdict(set)\n",
    "        # c_mat1={}\n",
    "        # r_mat2={}\n",
    "        c_mat2=defaultdict(set)\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat1[0])):\n",
    "                r_mat1[i].add(j)\n",
    "\n",
    "        for i in range(len(mat2)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                c_mat2[j].add(i)\n",
    "\n",
    "        ans=[[0]*(len(mat2[0]))  for i in range(len(mat1))]\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                if i in r_mat1 and j in c_mat2:\n",
    "                    t=0\n",
    "                    for v1 in r_mat1[i]:\n",
    "                        if v1 in c_mat2[j]:\n",
    "                            t+=mat1[i][v1]*mat2[v1][j]\n",
    "                    \n",
    "                    ans[i][j]=t\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat1)\n",
    "        k = len(mat1[0])\n",
    "        n = len(mat2[0])\n",
    "\n",
    "        mat1_row = [set() for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                mat1_row[i].add(j)\n",
    "        \n",
    "        mat2_col = [set() for _ in range(n)]\n",
    "        for i in range(k):\n",
    "            for j in range(n):\n",
    "                mat2_col[j].add(i)\n",
    "        \n",
    "        result = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                idx_set = mat1_row[i] & mat2_col[j]\n",
    "                for idx in idx_set:\n",
    "                    result[i][j] += mat1[i][idx] * mat2[idx][j]\n",
    "        \n",
    "        return result\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        r_mat1=defaultdict(set)\n",
    "        # c_mat1={}\n",
    "        # r_mat2={}\n",
    "        c_mat2=defaultdict(set)\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat1[0])):\n",
    "                r_mat1[i].add(j)\n",
    "\n",
    "        for i in range(len(mat2)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                c_mat2[j].add(i)\n",
    "\n",
    "        ans=[[0]*(len(mat2[0]))  for i in range(len(mat1))]\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                if i in r_mat1 and j in c_mat2:\n",
    "                    t=0\n",
    "                    for v1 in r_mat1[i]:\n",
    "                        if v1 in c_mat2[j]:\n",
    "                            t+=mat1[i][v1]*mat2[v1][j]\n",
    "                    \n",
    "                    ans[i][j]=t\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        r_mat1=defaultdict(set)\n",
    "        # c_mat1={}\n",
    "        # r_mat2={}\n",
    "        c_mat2=defaultdict(set)\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat1[0])):\n",
    "                r_mat1[i].add(j)\n",
    "\n",
    "        for i in range(len(mat2)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                c_mat2[j].add(i)\n",
    "\n",
    "        ans=[[0]*(len(mat2[0]))  for i in range(len(mat1))]\n",
    "        for i in range(len(mat1)):\n",
    "            for j in range(len(mat2[0])):\n",
    "                if i in r_mat1 and j in c_mat2:\n",
    "                    t=0\n",
    "                    v=r_mat1[i]&c_mat2[j]\n",
    "                    for v1 in v:\n",
    "                        # if v1 in c_mat2[j]:\n",
    "                        t+=mat1[i][v1]*mat2[v1][j]\n",
    "                    \n",
    "                    ans[i][j]=t\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    # def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "    #     m1 = np.array(mat1)\n",
    "    #     m2 = np.array(mat2)\n",
    "    #     return m1.dot(m2).tolist()\n",
    "    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat1)\n",
    "        k = len(mat2)\n",
    "        n = len(mat2[0])\n",
    "        ans = [[0]* n for i in range(m)]\n",
    "        # print(m,n,k)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for t in range(k):\n",
    "                    ans[i][j]+=mat1[i][t]*mat2[t][j]\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
